#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <assert.h>
#include <stdlib.h>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
using namespace std;
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <Types.h>
#include <DagMtx.h>
#include <Defines.h>
#include <Profiler.h>
#include <DedupMem.h>
#include <Statistics.h>
#include <LoadMatrix.h>
#include <IteratorRegister.h>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void CheckNumPartsVersusTreeDegree( const U32 deg, const U32 numParts ) {
   U64 logceil = LogXCeil( numParts, deg );
   U64 test = 1;
   while( logceil ) {
      test *= deg;
      logceil--;
   }
   assert( test == numParts );
}
U64 CalculateResetInterval( const U64 nnz, const U32 deg, const U32 numParts ) {

   assert( numParts > 0 );
   if( numParts == 1 ) {
      return 0ULL;
   }
   
   CheckNumPartsVersusTreeDegree( deg, numParts );
   
   // hgt : tree height in this tree degree
   // sub : amount to subtract from that height
   // rsi : the reset interval
   U64 effNNZ = 2 * nnz;
   U64 sub = LogXCeil( numParts, deg );
   U64 hgt = LogXCeil( effNNZ,   deg );
   U64 count = hgt - sub;
   U64 rsi = 1ULL;
   while( count ) {
      rsi *= deg;
      count--;
   }
   rsi >>= 1;
   return rsi;

}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void PrintIntToDAGNode( FILE * DAG, const U32 deg, const U32 intVal ) {
   U32 numWords = deg >> 1;
   U32 numZeros = numWords - 1;
   for( U32 zIdx = 0; zIdx < numZeros; zIdx++ ) {
      fprintf( DAG, "%016x ", 0 );
   }
   fprintf( DAG, "%016x\n", intVal );
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template< typename node_t > void WriteNodesToDAGFile( FILE * DAG, const vector< node_t > & nodes, const U32 deg ) {

   const U32 numWords = deg >> 1;
   LSU v;

   fprintf( DAG, "# begin nodes\n" );
   // -- TODO -- remove -- cout << "WriteNodesToDAGFile(): nodes.size() = " << nodes.size() << endl;
   for( U32 nodeIdx = 0; nodeIdx < nodes.size(); nodeIdx++ ) {
      
      const node_t & node = nodes[ nodeIdx ];

      // -- TODO -- remove -- cout << "WriteNodesToDAGFile(): nodeIdx = " << SETHEX(8) << deg*nodeIdx << ", node = ";
      for( U32 wordIdx = 0; wordIdx < numWords; wordIdx++ ) {

         // -- TODO -- remove -- const U32 numPtrs = deg; // 4
         // -- TODO -- remove -- const U32 ptrIdx  = wordIdx  << 1; // 0, 2
         // -- TODO -- remove -- const U32 offset  = numPtrs - ptrIdx; // 4, 2
         // -- TODO -- remove -- cout << SETHEX(8) << node.s[ offset - 1 ] << ", " << SETHEX(8) << node.s[ offset - 2 ] << " (" << setw(5) << SETFIX(1) << node.d[ numWords - 1 - wordIdx ] << SETDEC(0) << ") ";
         
         v.l = node.l[ numWords - 1 - wordIdx ];
         #ifdef __MAC_OSX__
         fprintf( DAG, "%016llx ", v.l );
         #else
         fprintf( DAG, "%016lx ",  v.l );
         #endif
         
      }
      // -- TODO -- remove -- cout << endl;
      fprintf( DAG, "\n" );
   }
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template < typename node_t > void WriteDAGFileStats( const DagMtx< node_t > & dagmtx, FILE * DAG ) {

   assert( dagmtx.dagStats.size() == dagmtx.arrStats.size() );
   const U32 numDags = dagmtx.arrStats.size();

   for( U32 i = 0; i < numDags; i++ ) {
      
      fprintf( DAG, "#\n" );
      fprintf( DAG, "# arrName: %s\n", dagmtx.arrNames[i].c_str() );
      dagmtx.arrStats[i].WriteToFile( DAG );
      
      fprintf( DAG, "#\n" );
      fprintf( DAG, "# dagName: %s\n", dagmtx.dagNames[i].c_str() );
      dagmtx.dagStats[i].WriteToFile( DAG );
   }
   dagmtx.WriteComparitiveStatisticsToFile( DAG );
}
template < typename node_t > void WriteDAGFileHeader( const DagMtx< node_t > & dagmtx, FILE * DAG ) {
   
   assert( dagmtx.dagHgts.size() == dagmtx.dagRootIdxs.size() );
   
   U32 numDAGs  = dagmtx.dagHgts.size();
   U32 numNodes = dagmtx.nodes.size();
   
   #ifdef __MAC_OSX__
   const char u64fmt[] = "%llu\n";
   #else
   const char u64fmt[] = "%lu\n";
   #endif
   const char u32fmt[] = "%u\n";
   
   // put meta data into file
   fprintf( DAG, u64fmt, dagmtx.meta.m   );  // m: row dim
   fprintf( DAG, u64fmt, dagmtx.meta.n   );  // n: col dim
   fprintf( DAG, u64fmt, dagmtx.meta.nnz );  // nnz
   fprintf( DAG, u32fmt, numNodes        );  // numNodes
   fprintf( DAG, u32fmt, numDAGs         );  // numDAGs
   for( U32 dagIdx = 0; dagIdx < numDAGs; dagIdx++ ) {
      
      U32 rootIdx = dagmtx.dagRootIdxs [ dagIdx ];
      U32  dagHgt = dagmtx.dagHgts     [ dagIdx ];
      // -- TODO -- remove -- cout << "WriteDAGFileHeader(): rootIdx = " << SETHEX(8) << (dagmtx.deg)*rootIdx << endl;
      // -- TODO -- remove -- cout << "WriteDAGFileHeader():  dagHgt = " << SETDEC(0) <<    dagHgt << endl;
      fprintf( DAG, u64fmt, rootIdx );  // rootIdx
      fprintf( DAG, u32fmt,  dagHgt );  // DAG height
   }
   WriteDAGFileStats( dagmtx, DAG );
}
template < typename node_t > void WriteIR_DAGFile( const DagMtx< node_t > & dagmtx ) {
   
   FILE * DAG;
   DAG = fopen( dagmtx.name.c_str(), "w" );
   // -- TODO -- remove -- cout << "WriteIR_DAGFile(): fn = " << dagmtx.name << endl;
   WriteDAGFileHeader( dagmtx, DAG );
   WriteNodesToDAGFile( DAG, dagmtx.nodes, dagmtx.deg );
   fclose( DAG );
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template < typename node_t > void IRConvertSparseArrayOfDoublesToDAG( DagMtx< node_t > & dagmtx, DedupMem< node_t > & ddm, const bool pcEnable, const map< U64, double > & spa ) {

   IteratorRegister< node_t, double > IR( dagmtx.deg, pcEnable, ddm );
         
   map< U64, double >::const_iterator leafIt;

   LSU leafV;
   U64 leafPos;
   
   for( leafIt = spa.begin(); leafIt != spa.end(); leafIt++ ) {
      
      leafPos = leafIt->first;
      leafV.d = leafIt->second;
      
      if( leafV.l != 0ULL ) {
         // -- TODO -- remove -- cout << "leafPos = " << SETDEC( 6 ) << leafPos << ", leafVal = " << leafV.d << endl;
         IR.SetLeafPos( leafPos );
         IR.SetLeafVal( leafV.d );
      }
   }
   IR.Commit( dagmtx );
   IR.Audit();
}
template < typename node_t > void IRConvertSparseArrayOfS32ToDAG( DagMtx< node_t > & dagmtx, DedupMem< node_t > & ddm, const bool pcEnable, const map< U32, S32 > & spa ) {

   IteratorRegister< node_t, S32 > IR( dagmtx.deg, pcEnable, ddm );
   
   map< U32, S32 >::const_iterator leafIt;
   
   for( leafIt = spa.begin(); leafIt != spa.end(); leafIt++ ) {
      
      const U64  leafPos = leafIt->first;
      const S32  leafVal = leafIt->second;
      
      if( leafVal != 0 ) {
         IR.SetLeafPos( leafPos );
         IR.SetLeafVal( leafVal );
      }
   }
   IR.Commit( dagmtx );
   IR.Audit();
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void InterleaveRowBreaks( map< U32, S32 > & colIdxs, map< U32, S32 > & rowPtrs, const U32 resetInterval ) {
   
   U32 m = rowPtrs.size() - 1;
   
   map< U32, S32 > retIdxs;
   U32 numRowsBroken = 1;
   U32 numIdxs = colIdxs.size();
   
   for( U32 i = 0; i < ( numIdxs << 1 ); i++ ) {
      retIdxs[ i ] = 0;
   }
   
   for( U32 rowIdx = 0; rowIdx < m; rowIdx++ ) {
      S32 beg = rowPtrs[ rowIdx + 0 ];
      S32 end = rowPtrs[ rowIdx + 1 ];
      if( end > beg ) {
         retIdxs[ beg << 1 ] = numRowsBroken;
         numRowsBroken = 1;
         for( S32 oldIdx = beg; oldIdx < end; oldIdx++ ) {
            S32 newIdx = oldIdx << 1;
            retIdxs[ newIdx + 1 ] = colIdxs[ oldIdx ];
         }
      }
      else {
         numRowsBroken++;
      }
   }
   if( resetInterval != 0ULL ) {
      U32 numEntries = retIdxs.size() >> 1;
      U32 rowCount = 0;
      for( U32 idx = 0; idx < numEntries; idx++ ) {
         if( idx % resetInterval == 0 ) {
            retIdxs[ idx << 1 ] += rowCount;
            rowCount = retIdxs[ idx << 1 ];
         }
         else {
            rowCount += retIdxs[ idx << 1 ];
         }
      }
   }
   colIdxs = retIdxs;
}
void InterleaveWithZeros( map< U64, double > & spa ) {
   
   map< U64, double > tmp = spa;
   spa.clear();
   
   map< U64, double >::iterator it;
   
   for( it = tmp.begin(); it != tmp.end(); it++ ) {
      U64    idx = it->first;
      double val = it->second;
      
      spa[ 2*idx ] = val;
   }
}
template< typename T > void DeltaEncode( map< U32, T > & v, const U32 resetInterval ) {

   const U32 num = v.size();
      
   T prev = 0;
   T diff = 0;
   T curr = 0;
   
   for( U32 idx = 0; idx < num; idx++ ) {
      if( resetInterval != 0 ) {
         if( idx % resetInterval == 0 ) {
            prev = v[ idx ];
            v[ idx ] -= 1;
            continue;
         }
      }
      curr = v[ idx ];
      diff = curr - prev;
      prev = curr;
      v[ idx ] = diff - 1;
   }
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void PadCSRRowsToModResetInterval( map< U64, double > & nnzVals, map< U32, S32 > & colIdxs, map< U32, S32 > & rowPtrs, const U32 resetInterval ) {

   const bool verbose = false;
   U64 numAligned = 0ULL;
   U64 numPadded  = 0ULL;
   U32 cumsum     = 0;
   
   cout << "==== Entering PadCSRRowsToModResetInterval ====" << endl;
   if( resetInterval == 0 ) {
      cout << "==== Leaving  PadCSRRowsToModResetInterval ====" << endl;
      return;
   }
   
   U64 m = rowPtrs.size() - 1;
   map< U64, vector< double > > rows;
   map< U64, vector<    U32 > > idxs;
   
   
   for( U64 rowIdx = 0ULL; rowIdx < m; rowIdx++ ) {
      U64 beg = rowPtrs[ rowIdx + 0 ];
      U64 end = rowPtrs[ rowIdx + 1 ];
      U64 num = end - beg;
      cumsum += num;
      if( cumsum == resetInterval ) {
         numPadded++;
         numAligned++;
         if( verbose ) {
            cout << numPadded << "padded, row boundary magically aligned to partition boundary" << endl;
         }
         cumsum = 0;
      }
      else if( cumsum  > resetInterval ) {
         numPadded++;
         if( verbose ) {
            cout << numPadded << "padded, padding row to partition boundary" << endl;
         }
         cumsum -= num;
         while( cumsum < resetInterval ) {

            U64 lci = idxs[rowIdx - 1][ idxs[rowIdx - 1].size() - 1 ];
            rows[ rowIdx-1 ].push_back( 0ULL );
            idxs[ rowIdx-1 ].push_back( lci  );
            cumsum++;
            
         }
         cumsum = num;
      }
      for( U64 i = beg; i < end; i++ ) {
         rows[ rowIdx ].push_back( nnzVals[i] );
         idxs[ rowIdx ].push_back( colIdxs[i] );
      }
   }
   
   nnzVals.clear();
   colIdxs.clear();
   rowPtrs.clear();
   
   rowPtrs[ 0 ] = 0;
   U64 nnzIdx   = 0;
   
   for( U32 rowIdx = 0; rowIdx < m; rowIdx++ ) {
      for( U32 i = 0; i < rows[ rowIdx ].size(); i++ ) {
         nnzVals[ nnzIdx ] = rows[ rowIdx ][ i ];
         colIdxs[ nnzIdx ] = idxs[ rowIdx ][ i ];
         nnzIdx++;
      }
      rowPtrs[ rowIdx + 1 ] = rows[ rowIdx ].size() + rowPtrs[ rowIdx ];
   }
   cout << "totNumPadded:  " << numPadded  << endl;
   cout << "numPreAligned: " << numAligned << endl;
   cout << "==== Leaving PadCSRRowsToModResetInterval ====" << endl;
}
void PadCSRRowsToMod4( map< U64, double > & nnzVals, map< U32, S32 > & colIdxs, map< U32, S32 > & rowPtrs ) {

   U32 m = rowPtrs.size() - 1;
   map< U32, vector< double > > rows;
   map< U32, vector<    U64 > > idxs;

   for( U32 rowIdx = 0; rowIdx < m; rowIdx++ ) {
      U32 beg = rowPtrs[ rowIdx + 0 ];
      U32 end = rowPtrs[ rowIdx + 1 ];
      U32 num = end - beg;
      U32 lci = 0;
      for( U64 i = beg; i < end; i++ ) {
         rows[ rowIdx ].push_back( nnzVals[i] );
         idxs[ rowIdx ].push_back( colIdxs[i] );
         lci = colIdxs[i];
      }
      while( num % 4) {
         rows[ rowIdx ].push_back( 0.0 );
         idxs[ rowIdx ].push_back( lci );
         num++;
      }
   }

   nnzVals.clear();
   colIdxs.clear();
   rowPtrs.clear();
   
   rowPtrs[ 0ULL ] = 0;
   
   U32 nnzIdx = 0;
   for( U32 rowIdx = 0; rowIdx < m; rowIdx++ ) {
      for( U32 i = 0; i < rows[ rowIdx ].size(); i++ ) {
         nnzVals[ nnzIdx ] = rows[ rowIdx ][ i ];
         colIdxs[ nnzIdx ] = idxs[ rowIdx ][ i ];
         nnzIdx++;
      }
      rowPtrs[ rowIdx + 1 ] = rows[ rowIdx ].size() + rowPtrs[ rowIdx ];
   }
}
void SparseArray2CSRArrays( const map< U64, double > & spa, const MatrixProperties & mtxMetaData, map< U64, double > & nnzVals, map< U32, S32 > & colIdxs, map< U32, S32 > & rowPtrs ) {
   // spa: the input sparse array
   // the keys are indices into the array where non-zero entries exist
   // the index itself implies the row column value -- the mapping from
   // index to row/col is format specific, e.g., for row major order:
   // ... row = index / n
   // ... col = index % n
   // for an m by n matrix
   // here (CSR format), the underlying mapping row major
   U64 nnzIdx  = 0ULL;
   U32 prevRow = 0;
   U32 ptrIdx  = 0;
   U32 nnz = spa.size();
   
   U64 p = 0ULL;
   U32 m = RoundUpToPow2( mtxMetaData.m );
   U32 n = RoundUpToPow2( mtxMetaData.n );
   
   double v;
   
   map< U64, double >::const_iterator it;
   for( it = spa.begin(); it != spa.end(); it++ ) {
      if( p != 0 ) { assert( it->first > p ); }
      
      p = it->first;
      v = it->second;
      // cout << "spa[ " << p << " ] = " << v << endl;
      U64 r = Pos2RowRMA( p, m, n );
      U64 c = Pos2ColRMA( p, m, n );
      nnzVals[ nnzIdx ] = v;
      colIdxs[ nnzIdx ] = c-1;
      while( r > prevRow) {
         rowPtrs[ ptrIdx ] = nnzIdx;
         ptrIdx++;
         prevRow++;
      }
      nnzIdx++;
   }
   while( mtxMetaData.m >= prevRow ) {
      rowPtrs[ ptrIdx ] = nnzIdx;
      ptrIdx++;
      prevRow++;
   }
   assert( rowPtrs[ rowPtrs.size() - 1 ] == ((S64)nnz) );
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void AddPatternMtxToNZDSparseArray( const U64 m, const U64 n, map< U64, double > & spa, const vector< U64 > & posvec, const U32 deg ) {

   LSU v;
   map< U64, U64 > pattMap;
   set< U64 >      visited;
   assert( spa.size() == 0 );
   
   // create the pattern mtx values
   for( U64 posIdx = 0ULL; posIdx < posvec.size(); posIdx++ ) {
      U64 pos = posvec[ posIdx ];
      U64 posIdx = pos >> 6ULL;
      U64 bitPos = pos & 63ULL;
      
      visited.insert( posIdx );
      if( pattMap.find( posIdx ) != pattMap.end() ) {
         pattMap[ posIdx ] |= ( 1ULL << bitPos );
      }
      else {
         pattMap[ posIdx ]  = ( 1ULL << bitPos );
      }
   }
   
   set< U64 >::iterator it;
   for( it = visited.begin(); it != visited.end(); it++ ) {
      v.l = pattMap[ *it ];
      spa[ *it ] = v.d;
   }

}
void SparseArrayToNZDLists( const map< U64, double > & inpSpa, map< U64, double > & outSpa, vector< U64 > & posvec ) {

   double v;
   U64 numEl = 0ULL;
   map< U64, double >::const_iterator it;
   for( it = inpSpa.begin(); it != inpSpa.end(); it++ ) {
      posvec.push_back( it->first );
      numEl++;
   }
   assert( numEl == inpSpa.size() );
   
   U64 posIdx = 0ULL;   
   for( U64 elIdx = 0ULL; elIdx < numEl; elIdx++ ) { 
      v = inpSpa.find( posvec[ elIdx ] )->second;
      outSpa[ posIdx ] = v;
      posIdx++;
   }
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template< typename T > void RMASequence( const string & mtxFileName, const string & hcdFileName, const U64 deg, const U64 numParts ) {
   
   assert( numParts == 1 );
   Profiler prof;
   const string fmt = "RMA";
   const bool pcEnable = true;

   DagMtx   < T > dagmtx( hcdFileName, deg );
   DedupMem < T > ddm( deg );
   map< U64, double > spa;
   
   prof.Start( "MtxMarket2SparseArray" );
   MtxMarket2SparseArray( mtxFileName, fmt, spa, dagmtx.meta );
   prof.Stop();
   
   dagmtx.CalculateLogicallyDenseArrStats();
   
   prof.Start( "ConvertSparseArrayToDAG" );
   IRConvertSparseArrayOfDoublesToDAG < T > ( dagmtx, ddm, pcEnable, spa );
   prof.Stop();
   
   prof.Start( "SerializeNodes" );
   ddm.SerializeNodes( dagmtx.nodes );
   prof.Stop();
   
   prof.Start( "WriteDAGFile" );
   WriteIR_DAGFile( dagmtx );
   prof.Stop();
}
template< typename T > void QTSSequence( const string & mtxFileName, const string & hcdFileName, const U64 deg, const U64 numParts ) {
   
   assert( numParts == 1 );
   Profiler prof;
   const string fmt = "QTS";
   const bool pcEnable = true;

   DagMtx< T > dagmtx( hcdFileName, deg );
   DedupMem < T > ddm( deg );
   map< U64, double > spa;
   
   prof.Start( "MtxMarket2SparseArray" );
   MtxMarket2SparseArray( mtxFileName, fmt, spa, dagmtx.meta );
   prof.Stop();

   dagmtx.CalculateLogicallyDenseArrStats();
   
   prof.Start( "InterleaveWithZeros" );
   InterleaveWithZeros( spa );
   prof.Stop();
   
   prof.Start( "ConvertSparseArrayToDAG" );
   IRConvertSparseArrayOfDoublesToDAG < T > ( dagmtx, ddm, pcEnable, spa );
   prof.Stop();
   
   prof.Start( "SerializeNodes" );
   ddm.SerializeNodes( dagmtx.nodes );
   prof.Stop();
   
   prof.Start( "WriteDAGFile" );
   WriteIR_DAGFile( dagmtx );
   prof.Stop();
}
template< typename T > void CSRSequence( const string & mtxFileName, const string & hcdFileName, const U64 deg, const U64 numParts ) {
   
   assert( numParts == 1 );
   Profiler prof;
   const string fmt = "CSR";
   const bool pcEnable = true;

   DagMtx< T > dagmtx( hcdFileName, deg );
   DedupMem < T > ddm( deg );
   
   map< U64, double > spa;
   map< U64, double > nnzVals;
   map< U32, S32    > colIdxs;
   map< U32, S32    > rowPtrs;

   prof.Start( "MtxMarket2SparseArray" );
   MtxMarket2SparseArray( mtxFileName, fmt, spa, dagmtx.meta );
   prof.Stop();
   
   dagmtx.CalculateCompressedArrStats();
   
   prof.Start( "SparseArray2CSRArrays" );
   SparseArray2CSRArrays( spa, dagmtx.meta, nnzVals, colIdxs, rowPtrs );
   spa.clear();
   prof.Stop();
   
   prof.Start( "DeltaEncode -- colIdxs and rowPtrs " );
   DeltaEncode( colIdxs, 0 );
   DeltaEncode( rowPtrs, 0 );
   prof.Stop();
   // 
   // 
   // # TODO - put common memline encoding into action, if beneficial...
   // prof.Start( "CommonMemLineEncode" )
   // colIdxsBaseLine = CommonMemLineEncode( colIdxs, deg, encode = False )
   // rowPtrsBaseLine = CommonMemLineEncode( rowPtrs, deg, encode = False )
   // prof.Stop()
   // 
   assert( nnzVals.size() == colIdxs.size() );
   prof.Start( "ConvertSparseArrayToDAG: non-zero list" );
   IRConvertSparseArrayOfDoublesToDAG < T > ( dagmtx, ddm, pcEnable, nnzVals ); nnzVals.clear();
   prof.Stop();
   prof.Start( "ConvertSparseArrayToDAG: column indices" );
   IRConvertSparseArrayOfS32ToDAG     < T > ( dagmtx, ddm, pcEnable, colIdxs ); colIdxs.clear();
   prof.Stop();
   prof.Start( "ConvertSparseArrayToDAG: row pointers" );
   IRConvertSparseArrayOfS32ToDAG     < T > ( dagmtx, ddm, pcEnable, rowPtrs ); rowPtrs.clear();
   prof.Stop();
   
   prof.Start( "SerializeNodes" );
   ddm.SerializeNodes( dagmtx.nodes );
   prof.Stop();

   prof.Start( "WriteDAGFile" );
   WriteIR_DAGFile( dagmtx );
   prof.Stop();
}
template< typename T > void COOSequence( const string & mtxFileName, const string & hcdFileName, const U64 deg, const U64 numParts ) {
   
   Profiler prof;
   const string fmt = "COO";
   const bool pcEnable = true;

   DagMtx   < T > dagmtx( hcdFileName, deg );
   DedupMem < T > ddm( deg );
   
   map< U64, double > spa;
   map< U64, double > nnzVals;
   map< U32, S32    > colIdxs;
   map< U32, S32    > rowPtrs;
   
   prof.Start( "MtxMarket2SparseArray" );
   MtxMarket2SparseArray( mtxFileName, fmt, spa, dagmtx.meta );
   prof.Stop();
   
   dagmtx.CalculateHybridArrStats();
   
   prof.Start( "SparseArray2CSRArrays" );
   SparseArray2CSRArrays( spa, dagmtx.meta, nnzVals, colIdxs, rowPtrs );
   spa.clear();
   prof.Stop();
   
   if( deg == 4 ) {
      prof.Start( "PaddRowsToMod4" );
      PadCSRRowsToMod4( nnzVals, colIdxs, rowPtrs );
      prof.Stop();
   }
   
   U64 nnz = nnzVals.size();
   assert( ((S64)nnz) == rowPtrs[ rowPtrs.size() - 1 ] );
   
   U64 resetInterval = CalculateResetInterval( nnz, deg, numParts );
   
   prof.Start( "PaddRowsToModResetInterval" );
   PadCSRRowsToModResetInterval( nnzVals, colIdxs, rowPtrs, resetInterval );
   dagmtx.meta.nnz = rowPtrs[ rowPtrs.size() - 1 ];
   prof.Stop();
   
   prof.Start( "DeltaEncode -- colIdxs and rowPtrs " );
   DeltaEncode( colIdxs, resetInterval );
   prof.Stop();
      
   prof.Start( "Interleave row breaks into col indices" );
   InterleaveRowBreaks( colIdxs, rowPtrs, resetInterval );
   rowPtrs.clear();
   prof.Stop();
      
   // ## TODO - put common memline encoding into action, if beneficial...
   // #prof.Start( "CommonMemLineEncode" )
   // #colIdxsBaseLine = CommonMemLineEncode( colIdxs, deg, encode = False )
   // #prof.Stop()
   
   assert( 2 * nnzVals.size() == colIdxs.size() );
   prof.Start( "ConvertSparseArrayToDAG: non-zero list" );
   IRConvertSparseArrayOfDoublesToDAG < T > ( dagmtx, ddm, pcEnable, nnzVals ); nnzVals.clear();
   prof.Stop();
   prof.Start( "ConvertSparseArrayToDAG: row/col indices" );
   IRConvertSparseArrayOfS32ToDAG     < T > ( dagmtx, ddm, pcEnable, colIdxs ); colIdxs.clear();
   prof.Stop();
   
   prof.Start( "SerializeNodes" );
   ddm.SerializeNodes( dagmtx.nodes );
   prof.Stop();

   prof.Start( "WriteDAGFile" );
   WriteIR_DAGFile( dagmtx );
   prof.Stop();
}
template< typename T > void NZDSequence( const string & mtxFileName, const string & hcdFileName, const U64 deg, const U64 numParts ) {
   
   assert( numParts == 1 );
   Profiler prof;
   const bool pcEnable = true;
   
   DagMtx< T > dagmtx( hcdFileName, deg );
   DedupMem < T > ddm( deg );
   
   map< U64, double > nzvspa; // non-zero values sparse array
   map< U64, double > nzlspa; // list of non-zeros
   map< U64, double > qtsspa; // pattern matrix

   vector< U64 >      posvec; // position vector
   
   prof.Start( "MtxMarket2SparseArray" );
   MtxMarket2SparseArray( mtxFileName, "QTS", nzvspa, dagmtx.meta );
   prof.Stop();
   
   dagmtx.CalculateHybridArrStats();
      
   U64 m = dagmtx.meta.m;
   U64 n = dagmtx.meta.n;
   
   m = RoundUpToPowX( m, deg );
   n = RoundUpToPowX( n, deg );
   
   prof.Start( "SparseArrayToNZDLists" );
   SparseArrayToNZDLists( nzvspa, nzlspa, posvec );
   nzvspa.clear();
   prof.Stop();
   
   prof.Start( "AddPatternMtxToNZDSparseArray" );
   AddPatternMtxToNZDSparseArray( m, n, qtsspa, posvec, deg );
   posvec.clear();
   prof.Stop();
   
   prof.Start( "ConvertSparseArrayToDAG: non-zero list" );
   IRConvertSparseArrayOfDoublesToDAG < T > ( dagmtx, ddm, pcEnable, nzlspa ); nzlspa.clear();
   prof.Stop();
   prof.Start( "ConvertSparseArrayToDAG: pattern matrix" );
   IRConvertSparseArrayOfDoublesToDAG < T > ( dagmtx, ddm, pcEnable, qtsspa ); qtsspa.clear();
   prof.Stop();
   
   prof.Start( "SerializeNodes" );
   ddm.SerializeNodes( dagmtx.nodes );
   prof.Stop();
   
   prof.Start( "WriteDAGFile" );
   WriteIR_DAGFile( dagmtx );
   prof.Stop();
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
int main( int argc, char ** argv ) {

   if( argc < 6 ) {
      cout << "usage: " << argv[0] << " [RMA|QTS|NZD|CSR|COO] <mtxFile> <hcdFile> <deg> <numParts>" << std::endl;
      exit( -1 );
   }
   
   string mtxFmt      = argv[1];
   string mtxFileName = argv[2];
   string hcdFileName = argv[3];
   
   U32 deg      = atoi( argv[4] );
   U32 numParts = atoi( argv[5] );

   assert( hcdFileName != "stdout" );
   assert( hcdFileName != "stderr" );

   DEBUG_PRINT( "main():  Mtx2Dag" );
   DEBUG_PRINT( "... mtxFmt = " << mtxFmt );
   
   if( deg == 2 ) {
      if     ( mtxFmt == "RMA" )  
         RMASequence< BNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "QTS" )  QTSSequence< BNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "CSR" )  CSRSequence< BNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "COO" )  COOSequence< BNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "NZD" )
         NZDSequence< BNode >( mtxFileName, hcdFileName, deg, numParts );
      else assert( false );
   }
   else if( deg == 4 ) {
      if     ( mtxFmt == "RMA" )
         RMASequence< QNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "QTS" )  QTSSequence< QNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "CSR" )  CSRSequence< QNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "COO" )  COOSequence< QNode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "NZD" )  NZDSequence< QNode >( mtxFileName, hcdFileName, deg, numParts );
      else assert( false );
   }
   else if( deg == 8 ) {
      if     ( mtxFmt == "RMA" )
         RMASequence< ONode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "QTS" )  QTSSequence< ONode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "CSR" )  CSRSequence< ONode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "COO" )  COOSequence< ONode >( mtxFileName, hcdFileName, deg, numParts );
      else if( mtxFmt == "NZD" )  NZDSequence< ONode >( mtxFileName, hcdFileName, deg, numParts );
      else assert( false );
   }
   else assert( false );
      
   return 0;
}
